#include <stdio.h>
#include <stdlib.h>
#include <string.h>


#define SIZE 4

struct Record{
    int          key;
    int          used;
    int          next;
    int          prev;
    char         firstName[40];
    char         lastName[80];
    char         street[100];
    unsigned int houseNumber;
    char         location[40];
    unsigned int age;
};


int getKey(int (*keyPool)[])
{
    int i=0;

    for(i=0;i<SIZE;i++){
      if ((*keyPool)[i]==0){
        (*keyPool)[i]=1;
        return i;
      }
    }
    return -1;
}

/**********************************************************************************
inserts record newRecord in list
returns
  1 if success
  0 if list is full
**********************************************************************************/
int insertRecord(struct Record list[], int *root, int (*keyPool)[], int (*indexOnKey)[],
                 struct Record newRecord)
{
  int retValue=0;
  int tmp=0;

  if (*root==-1)
    retValue=0;
  else{
   tmp=*root;
   *root=list[tmp].next;
   list[tmp]=newRecord;
   list[tmp].key=getKey(keyPool);
   list[*root].prev=-1;
   list[tmp].used=1;
   (*indexOnKey)[list[tmp].key]=tmp;
   list[tmp].next=-1;
   retValue=1;
  }

  return retValue;
}

int searchKey(struct Record list[],int key)
{
  int frame=0;
  int i=0;

  for (i=0;i<SIZE;i++){
    if (list[i].used == 1)
      if  (list[i].key==key){
        frame=i;
        break;
      }
  }
  if (i==SIZE)
    frame=-1;
  return frame;
}
int searchRecordFirstName(struct Record list[], char firstName[])
{
  int i=0;

  for(i=0;i<SIZE;i++){
    if(list[i].used==1 && strcmp(list[i].firstName,firstName)==0)
      return i;
  }
  return -1;
}

int clearFrame(struct Record list[],int * root, int (*keyPool)[], int (*indexOnKey)[], int frame)
{
    int retValue=1;
    int tmp=0;

    if(frame>SIZE)
      retValue=0;
    else if (list[frame].used==0)
           retValue=1;
    else{
      tmp=*root;
      *root=frame;
      list[tmp].prev=*root;
      list[frame].next=tmp;
      list[frame].used=0;
      (*keyPool)[list[frame].key]=0;
      (*indexOnKey)[list[frame].key]=-1;
      list[frame].key=-1;
      retValue=1;
    }
    return retValue;
}
void printList(struct Record list[])
{
  int i;

  printf("\n");
  for (i=0;i<SIZE;i++){
    printf(" key used next prev\n");
    printf("%4d %4d %4d %4d %s %s %s %d %s %d\n",list[i].key,list[i].used,list[i].next,list[i].prev,list[i].firstName,list[i].lastName,
                                    list[i].street, list[i].houseNumber, list[i].location,
                                    list[i].age);
  }
  printf("\n");
}

void printKeys(int (*keyPool)[])
{
    int i=0;

    printf("keys\n");
    for(i=0;i<SIZE;i++)
      printf("key: %d frame %d\n",i,(*keyPool)[i]);
}

void printIndex(int(*index)[])
{
    int i=0;

    printf("index\n");
    for(i=0;i<SIZE;i++)
      printf("index: %d frame %d\n",i,(*index)[i]);
}

int main()
{
    struct Record list[SIZE]={{0,0, 1,-1,"FirstName1","LastName1","Street1",1,"City1",1},
                              {1,0, 2, 1,"FirstName2","LastName1","Street1",1,"City1",1},
                              {2,0, 3, 2,"FirstName3","LastName1","Street1",1,"City1",1},
                              {3,0,-1, 3,"FirstName4","LastName1","Street1",1,"City1",1}};
    int (*keyPool)[SIZE];
    int tmp[SIZE]={0,0,0,0};
    int (*indexOnKey)[SIZE];
    int tmpIndex[SIZE]={-1,-1,-1,-1};
    int rootEmptyFramesList=0;
    int retValue=0;

    keyPool=&tmp;
    indexOnKey=&tmpIndex;
    struct Record r5 = {4,0,-1,-1,"FirstName5","LastName1","Street1",1,"City1",1};
    struct Record r6 = {5,0,-1,-1,"FirstName6","LastName1","Street1",1,"City1",1};
    struct Record r7 = {6,0,-1,-1,"FirstName7","LastName1","Street1",1,"City1",1};
    struct Record r8 = {7,0,-1,-1,"FirstName8","LastName1","Street1",1,"City1",1};
    struct Record r9 = {8,0,-1,-1,"FirstName9","LastName1","Street1",1,"City1",1};

    printf("Start\n");

    printf("rootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue = insertRecord(list,&rootEmptyFramesList,keyPool,indexOnKey,r5);
    printf("Add r5 \nrootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue = insertRecord(list,&rootEmptyFramesList,keyPool,indexOnKey,r6);
    printf("Add r6 \nrootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue = insertRecord(list,&rootEmptyFramesList,keyPool,indexOnKey,r7);
    printf("Add r7 \nrootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue = insertRecord(list,&rootEmptyFramesList,keyPool,indexOnKey,r8);
    printf("Add r8 \nrootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue = insertRecord(list,&rootEmptyFramesList,keyPool,indexOnKey,r9);
    if(retValue==0)
      printf("Add r9 \nERROR: table full. Record not added.\n");
    printf("rootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);

    retValue=clearFrame(list,&rootEmptyFramesList,keyPool,indexOnKey,1);
    printf("clear frame 1\nrootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue=clearFrame(list,&rootEmptyFramesList,keyPool,indexOnKey,3);
    printf("clear frame 3\nrootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue=clearFrame(list,&rootEmptyFramesList,keyPool,indexOnKey,2);
    printf("clear frame 2\nrootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue=clearFrame(list,&rootEmptyFramesList,keyPool,indexOnKey,0);
    printf("clear frame 0\nrootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue=searchKey(list,3);
    printf("add r9\nsearchKey result = %d\n",retValue);
    retValue = insertRecord(list,&rootEmptyFramesList,keyPool,indexOnKey,r9);
    printf("rootEmptyFramesList %d\n",rootEmptyFramesList);
    printList(list);
    retValue=searchKey(list,0);
    printf("searchKey result = %d\n",retValue);
    printKeys(keyPool);

    retValue=searchRecordFirstName(list,"FirstName9");
    printf("searchRecordFirstName result = %d\n",retValue);
    retValue=searchRecordFirstName(list,"FirstName8");
    printf("searchRecordFirstName result = %d\n",retValue);

    return 0;
}
